package com.algorithm.排序;

import com.algorithm.排序.model.Student;
import com.algorithm.排序.基于比较的排序.希尔排序;
import com.algorithm.排序.基于计数的排序.基数排序;
import com.algorithm.排序.基于计数的排序.计数排序;
import com.algorithm.排序.基于计数的排序.计数排序_优化;

import java.text.DecimalFormat;

//排序的公共父类
public abstract class Sort<E extends Comparable<E>> implements Comparable<Sort<E>>{
    protected E[] array;
    private int cmpCount;
    private int swapCount;
    private long time;
    private DecimalFormat fmt = new DecimalFormat("#.00"); //保留两位小数

    public void sort(E[] array) {
        if (array == null || array.length < 2)return;

        this.array = array;

        long begin = System.currentTimeMillis();
        sort();
        time = System.currentTimeMillis() - begin;
    }

    protected abstract void sort();

    /**
     * 返回值等于0 代表 array[i1] == array[i2]
     * 返回值小于0 代表 array[i1] < array[i2]
     * 返回值大于0 代表 array[i1] > array[i2]
     */
    protected int cmp(int i1, int i2) {
        cmpCount ++;
        return array[i1].compareTo( array[i2]);
    }

    //传入数组元素，直接比较数组的元素
    protected int cmp(E v1, E v2) {
        cmpCount ++;
        return v1.compareTo(v2);
    }

    //交换两个数组的元素的位置
    protected void swap(int i1, int i2){
        swapCount ++;
        E tmp = array[i1];
        array[i1] = array[i2];
        array[i2] = tmp;
    }

    private String numberString(int number) {
        if (number < 10000) return "" + number;

        if (number < 100000000) return fmt.format(number / 10000.0) + "万";
        return fmt.format(number / 100000000.0) + "亿";
    }

    @Override
    public String toString() {
        String timeStr = "耗时：" + (time / 1000.0) + "s(" + time + "ms)";
        String compareCountStr = "比较：" + numberString(cmpCount);
        String swapCountStr = "交换：" + numberString(swapCount);
        String stableStr = "稳定性：" + isStable();
        return "【" + getClass().getSimpleName() + "】\n"
                + stableStr + " \t"
                + timeStr + " \t"
                + compareCountStr + "\t "
                + swapCountStr + "\n"
                + "------------------------------------------------------------------";
    }

    private boolean isStable(){
        if (this instanceof 希尔排序)return false;
        if (this instanceof 计数排序)return false;
        if (this instanceof 计数排序_优化)return true;
        if (this instanceof 基数排序)return true;

        Student[] students = new Student[20];
        for (int i = 0; i < students.length; i++) {
            students[i] = new Student(i * 10, 10);
        }
        sort((E[]) students);
        for (int i = 1; i < students.length; i++) {
            int score = students[i].score;
            int prevScore = students[i - 1].score;
            if (score != prevScore + 10) return false;
        }
        return true;
    }

    @Override
    public int compareTo(Sort<E> o) {
        int result = (int)(this.time - o.time);
        if (result != 0) {
            return result;
        }

        result = swapCount - o.swapCount;
        if (swapCount != 0) {
            return result;
        }

        return cmpCount - o.cmpCount;
    }
}
